class Solution {
    /*
        把数组看做哈希表，空间复杂度O（1）
    */
    // -3 4 -100 -1
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        // 3 4 -1 1
        for (int i = 0; i < len; i++) {
            if (nums[i] <= 0)
                nums[i] = Integer.MAX_VALUE;
        }
        // 3 4 100 1
        for (int i = 0; i < len; i++) {
            int tmp = Math.abs(nums[i]);
            if (tmp >= 1 && tmp <= len) { // 标记
                int index = tmp - 1;
                if (nums[index] > 0)       // 数组中存在重复的数
                    nums[index] = -nums[index];
            }
        }
        // -3 4 -100 -1
        for (int i = 0; i < len; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }

        return len + 1;
    }
}

class Solution {
    /*
        使用哈希表，常规思路，空间复杂度O（N）
    */
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        int[] arr = new int[len+1];
        for(int i : nums){
            if(i>=1 && i<=len)
                arr[ i ] = 1;
        }
        for (int i = 1; i <= len; i++) {
            if(arr[i]==0)
                return i;
        }
        return len+1;
    }
}